package pers.sloera.leetcode.editor.cn;

/**
 * 极大极小游戏
 *
 * @author sloera
 * @date 2023-01-15 20:47:53
 */
class MinMaxGame {
    public static void main(String[] args) {
        Solution solution = new MinMaxGame().new Solution();
        // solution.minMaxGame(new int[]{1, 3, 5, 2, 4, 8, 2, 2});
        solution.minMaxGame(new int[]{999, 939, 892, 175, 114, 464, 850, 107});
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int minMaxGame(int[] nums) {
            if (nums.length == 1) {
                return nums[0];
            }
            return minMaxGame(nums, 0, nums.length, false);
        }

        private int minMaxGame(int[] array, int leftIndex, int length, boolean isMax) {
            int left;
            int right;
            if (length == 2) {
                left = array[leftIndex];
                right = array[leftIndex + 1];
            } else {
                left = minMaxGame(array, leftIndex, length >> 1, false);
                right = minMaxGame(array, leftIndex + (length >> 1), length >> 1, true);
            }
            return isMax ? Math.max(left, right) : Math.min(left, right);
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)

}
